#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>//rand()
#define rep(i,a,b) for(register long long i = (a);i <= (b);++i)
#define per(i,a,b) for(register long long i = (a);i >= (b);--i)
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;

int ans,n,m,dp[10000],a[15][15],u,v,w,dis[15],tmp;
int inf = 1e9+9;

inline void solve(int now){
    rep(i,1,n){
        if(((1 << (i-1)) & now) == 0) continue;
        rep(j,1,n){
            if(((1 << (j-1)) & now) == 0 && a[i][j] != inf){
                int nnow = now | (1 << (j-1));
                if(dp[ nnow ] > dp[now] + dis[i] * a[i][j]){
                    tmp = dis[j] , dis[j] = dis[i] , ++dis[j];
                    dp[ nnow ] = dp[now] + dis[i] * a[i][j];
                    solve(nnow);
                    dis[j] = tmp;
                }
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.in", "r", stdin);
    cin >> n >> m;

    ans = inf;
    rep(i,1,n) rep(j,1,n) a[i][j] = inf;    
    rep(i,1,m){
        cin >> u >> v >> w;
        a[u][v] = std::min(a[u][v],w);
        a[v][u] = std::min(a[v][u],w);
    }
    rep(i,1,n){
        rep(i,1,n) dis[i] = inf;
        rep(i,0,(1 << n) - 1) dp[i] = inf;
        dis[i] = 1;
        dp[1 << (i-1)] = 0;
        solve(1 << (i-1));
        ans = std::min(ans,dp[(1 << n)-1]);
    }
    cout << ans << "\n";

    return 0;
}